/*
 * @Author: szx
 * @Date: 2021-11-14 12:59:17
 * @LastEditTime: 2021-11-14 13:12:57
 * @Description:
 * @FilePath: \leetcode\100-199\117\117.js
 */

// Definition for a Node.
function Node(val, left, right, next) {
    this.val = val === undefined ? null : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
    this.next = next === undefined ? null : next;
}

/**
 * @param {Node} root
 * @return {Node}
 */
// var connect = function (root) {
//     if (!root) return null;
//     if (!root.right && !root.left) {
//         return root;
//     }
//     if(root.left)
//         root.left.next =  root.right;
//     if(root.next){
//         root.right.next = root.next.left;
//     }
//     connect(root.left);
//     connect(root.right);
//     return root;
// };
var connect = function(root) {
    if (root === null) {
        return null;
    }
    const queue = [root];
    while(queue.length){
        const n = queue.length
        let last = null;
        for (let i = 1; i <= n; ++i) {
            let f = queue.shift();
            if (f.left !== null) {
                queue.push(f.left);
            }
            if (f.right !== null) {
                queue.push(f.right);
            }
            if (i !== 1) {
                last.next = f;
            }
            last = f;
        }
    }
    return root;
};
